package 牛客.字符串;

/*
    给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。
    示例1
        输入  "1A2C3D4B56","B1D23CA45B6A"
        返回值 "123456"
 */
public class 最长公共子序列 {
    public String LCS (String str1, String str2) {
        int m = str1.length() - 1;
        int n = str2.length() - 1;
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int i,j;
        int[][] L = new int[m + 1][n + 1];
        int[][] S = new int[m + 1][n + 1];

        for (i = 0; i <= n; i++) {   //初始化第0行
            L[0][i] = 0;
        }
        for (i = 0; i <= m; i++) {    //初始化第0列
            L[i][0] = 0;
        }
        for (i = 0; i <= m ; i++) {
            for (j = 0; j <= n ; j++) {
                if (i == 0 || j == 0) {        //i == 0 或j == 0的情况要分开讨论，否则会越界
                    if (chars1[i] == chars2[j]) {
                        L[i][j] = 0 + 1;
                        S[i][j] = 1;
                    }
                }else {
                    if (chars1[i] == chars2[j]) {
                        L[i][j] = L[i - 1][j - 1] + 1;
                        S[i][j] = 1;
                    } else if (L[i][j - 1] >= L[i - 1][j]) {
                        L[i][j] = L[i][j - 1];
                        S[i][j] = 2;
                    } else {
                        L[i][j] = L[i - 1][j];
                        S[i][j] = 3;
                    }
                }
            }
        }
        i = m; j = n;
        StringBuilder z = new StringBuilder();
        while(i>=0 && j>=0){
            if(S[i][j] == 1){
                z.append(chars1[i]);
                i--;j--;
            }
            else if(S[i][j] == 2) j--;
            else i--;
        }
        if(z.length() == 0)
            return "-1";
        else
            return z.reverse().toString();
    }

    public static void main(String[] args) {
        最长公共子序列 obj = new 最长公共子序列();
        String str1 = "1A2C3D4B56";
        String str2 = "B1D23CA45B6A";
        String lcs = obj.LCS(str1, str2);
        System.out.println(lcs);

    }
}
